//https://leetcode.cn/problems/snapshot-array/description/?envType=daily-question&envId=2024-04-26


class SnapshotArray {
public:
    SnapshotArray(int length) {
        count = 0;
        cnt.resize(length);
    }
    
    void set(int index, int val) {
        cnt[index].emplace_back(count,val);
    }
    
    int snap() {
        return count++;
    }
    
    int get(int index, int snap_id) {
        // 二分查找出 snap_id 从后往前找 第一个小于 snap_id + 1 的, 这样就会包括 snap_id， 
        // 不用用 lower_bound, 然后就改为snap_id（找到第一个小于等于），因为不一定会等于，
        // 因为该 snap_id 快照更新过，但后面的val你是不确定的，用-1是拿来比较的，因为val >= 0,
        auto x = upper_bound( cnt[index].rbegin(),cnt[index].rend(),pair{snap_id+1,-1},greater<pair<int,int>>());
        return x == cnt[index].rend() ? 0 : x->second;
    }
private:
    int count;
    vector<vector<pair<int,int>>> cnt;
};



